package com.chapter4.graph.undirect;

/** 
 * @ClassName: CC 
 * @Description: 连通分量
 * @author minjun minjun@bw30.com
 * @date 2015-2-26 上午3:05:06 
 *  
 */
public class CC {
	
	//是否被访问过
	private boolean[] marked;
	
	//所属标识符
	private int[] id;
	
	//连通分量数
	private int count;
	
	public CC(Graph g){
		marked=new boolean[g.V()];
		id=new int[g.V()];
		//迭代所有元素
		for(int v=0;v<g.V();v++){
			//如果没有被访问
			if(!marked[v]){
				//访问所有与该节点相连通的节点，并更改访问状态
				dfs(g, v);
				//连通分量+1
				count++;
			}
		}
	}
	
	private void dfs(Graph g,int v){
		//将状态设置为已经访问过
		marked[v]=true;
		//设置所属标识符
		id[v]=count;
		for(int w:g.adj(v)){
			if(!marked[w]){
				//递归访问相连元素
				dfs(g, w);
			}
		}
	}
	
	/**
	 * 
	* @Title: connected 
	* @Description: 判断v和w是否连通 
	* @param @param v
	* @param @param w
	* @param @return    设定文件 
	* @return boolean    返回类型 
	* @throws
	 */
	public boolean connected(int v,int w){
		return id[v]==id[w];
	}
	
	/**
	 * 
	* @Title: count 
	* @Description: 连通分量数 
	* @param @return    设定文件 
	* @return int    返回类型 
	* @throws
	 */
	public int count(){
		return count;
	}
	
	/**
	 * 
	* @Title: id 
	* @Description: 节点v所属的连通分量标识符 
	* @param @param v
	* @param @return    设定文件 
	* @return int    返回类型 
	* @throws
	 */
	public int id(int v){
		return id[v];
	}
	
	public void printComponents(){
		int temp=-1;
		StringBuilder sb=new StringBuilder();
		for(int i=0;i<id.length;i++){
			if(temp!=id[i]){
				temp=id[i];
				sb.append("\n"+id[i]+":\t"+i);
			}else{
				sb.append("\t"+i);
			}
		}
		System.out.println(sb.toString());
	}
}
